//: [Previous](@previous)

/*:
 ### LeetCode上第206号问题：Reverse Linked List
 ```
 反转一个单链表。
 示例:
 
 输入: 1->2->3->4->5->NULL
 输出: 5->4->3->2->1->NULL
 进阶:
 
 你可以迭代或递归地反转链表。你能否用两种方法解决这道题？
 ```
 */

var list = SinglyLinkedList(arr: [1,2,3,4,5])

// 定义一个虚拟结点 循环赋值
func Solution(_ head: ListNode?) -> ListNode? {
    
    let dummyHead = ListNode(0)
    let newTemp: ListNode? = dummyHead
    var temp = head
    
    while temp != nil {
        let t = temp
        temp = temp?.next
        
        t?.next = newTemp?.next
        newTemp?.next = t
    }
    
    return dummyHead.next
}
print(list)
list.head = Solution(list.head)
print(list)

func Solution2(_ head: ListNode?) -> ListNode? {
    
    var temp = head
    var newHead: ListNode?
    
    while temp != nil {
        let next = temp?.next
        temp?.next = newHead
        newHead = temp
        temp = next
    }
    
    return newHead
}

print(list)
list.head = Solution2(list.head)
print(list)

// 递归调用
func Solution3(_ node: ListNode?) -> ListNode? {
    if node == nil || node?.next == nil {
        return node
    }
    
    let temp = Solution3(node?.next)
    node?.next?.next = node
    node?.next = nil
    
    return temp
}

print(list)
list.head = Solution3(list.head)
print(list)

//: [Next](@next)
